import java.util.Random;

//最小的K个元素
//测试链接 https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
public class InventoryManagement {
    public int[] inventoryManagement(int[] stock, int cnt) {
        qsort(stock,0,stock.length-1,cnt);//先对数组排序
        int[] ans = new int[cnt];
        for(int i = 0 ; i < cnt; i++){
            ans[i] = stock[i];
        }
        return ans;
    }

    public void qsort(int[] stock, int l, int r, int cnt){
        if(l >= r) return;

        int key = stock[new Random().nextInt(r - l + 1) + l];
        int left = l - 1, right = r + 1, i = l;
        while(i < right){
            if (stock[i] < key) swap(stock, ++left, i++);
            else if(stock[i] > key) swap(stock, --right, i);
            else i++;
        }
        int a = left - l + 1;
        int b = right - 1 - (left + 1) + 1 ;
        int c = r - right + 1;
        if(a >= cnt){
            qsort(stock,l,left,cnt);
        }else if(a + b >= cnt){
            return ;
        }else {
            qsort(stock,right,r, cnt - a - b);
        }

    }

    public void swap(int[] stock, int i, int j){
        int temp = stock[i];
        stock[i] = stock[j];
        stock[j] = temp;
    }
}
